iT邦幫忙

0

Leetcode 33. ( Search in Rotated Sorted Array )

  • 分享至 

  • xImage
  •  

In time, you will call me master -- Star Wars
https://leetcode.com/problems/search-in-rotated-sorted-array/

Description :

  • given a sorted array rotated one time sat a pivot point

  • given a target

  • find target index

  • return -1 if not found

  • Example :

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
nums = [4,5,6,7,0,1,2], target = 3
Output : -1

  • Soltuion:

    index 0 1 2 3 4 5 6
    origin 0 1 2 4 5 6 7
    given 4 5 6 7 0 1 2
  • method : view given rotated array as origin array without rotation

    • first use binary search to find rotate pivot point ( smallest point in given array )
    • we find 0 in the given array, and index is 4 ( rotation = 4 )
    • do binary search again
    • add a new variable realmid (mid + rotation = 4) % length => origin middle point
      • for example :
      • lo = 0 hi = 6 mid = 3 realmid = index : 0 (7%7) val : 4 (origin middle point)
  • code

    class Solution:
      """
      @param A: an integer rotated sorted array
      @param target: an integer to be searched
      @return: an integer
      """
      def search(self, A, target):
          # write your code here
          lo = 0
          hi = len(A)-1
          if len(A) == 0:
              return -1
          # binary search find smallest
          # we need to find smallest -- > 
          # which is the pivot point of the rotated list
          # so if mid value > hi value -- > 
          # we need to go to left side of mid to keep searching samllest value
          # if mid value < hi value -- > 
          # we need to go to right side of mid to keep searching smallest value
          while lo < hi :
              mid = lo + (hi-lo)//2
              print(mid)
              if A[mid] > A[hi]:
                  lo = mid +1 
              else:
                  hi = mid 
          # here lo == hi == rotate point == smallest value index
          rot = lo
          print("rot", rot)
          lo = 0
          hi = len(A)-1
          # do binary search again to the rotate list 
          # and use rot to find origin middle point
          while lo <= hi:
              mid = (lo+hi)//2
              realmid = (mid + rot) % len(A)
              print(A[realmid], realmid)
              if A[realmid] == target :
                  return realmid
              if A[realmid] < target:
                  lo = mid + 1
              else:
                  hi = mid - 1
          print(lo,mid , hi)
          return -1
    

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言